package cn.zhl.fuzadu;

/**
 * @program: demos
 * @description:
 * @author: 刘振华
 * @create: 2020-03-27 09:54
 **/
public class Fibonacci {
	//    n表示第几项
//    1  2  3  4  5  6  7...
//    0  1  1  2  3  5  8...
	public static int fib1(Integer n) {
//        1 + n-
		if (n < 3) {
			return n - 1;
		}
		return fib1(n - 1) + fib1(n - 2);
	}

	public static long fib2(int n) {
//        3+1+3(n-2)
		if (n < 2) {
			return n - 1;
		}
		long first = 0;
		long second = 1;
		for (int i = 0; i < n - 2; i++) {
			second += first;
			first = second - first;
		}
		return second;
	}

	//2147483647
//1836311903
	public static void main(String[] args) {
//        for(int i = 1;i<10;i++){
//            System.out.println(fib2(i));
//            System.out.println(fib1(i));
//        }
//        TimeTool.showTime("fib1", new TimeTool.Task() {
//            @Override
//            public void execute() {
//                System.out.println(fib1(45));
//            }
//        });
//        TimeTool.showTime("fib2", new TimeTool.Task() {
//            @Override
//            public void execute() {
//                System.out.println(fib2(45));
//            }
//        });

	}
}
